#include <iostream>
#include <list>
#include <unordered_map>
#include <utility>
using namespace std;
//实现O(1)复杂的的查找，删除和添加
class LRU{
public:
    LRU(int capacity)
    :_capacity(capacity)
    {

    }
    //查找,如果有，就移动到最开始的位子
    void put(int key,int value){
        auto it=_up.find(key);
        if(it!=_up.end()){
        //list<pair<int,int>>::iterator,这个迭代器指向的是list的一个结点,
        //结点的类型是pair<int,int>通过这个迭代器就可以实现value的修改
        it->second->second=value;             
        _lt.splice(_lt.begin(),_lt,it->second);
        }else{//如果没有这个键，就添加到第一个
              //分为两种情况，分别是容器满了和容器没满
            //容器满了
            if(_lt.size()==_capacity){
                auto lastnodes=_lt.back();
                _lt.pop_back();
                _up.erase(lastnodes.first);
            }
            //然后分别放到容器的最前面
            _lt.push_front({key,value});
            _up[key]=_lt.begin();
        }
    }    
    int get(int key){
        auto it=_up.find(key);
        if(it!=_up.end()){
            //找到了
            cout<<"find it"<<endl;
            return it->second->second;
        }else{
            //没找到
            cout<<"not found"<<endl;
            return -1;
        }
    }
    void display(){
        for(auto ele:_lt){
            cout<<ele.first<<" "<<ele.second<<endl;
        }
    }
        
private:
    int _capacity;
    list<pair<int,int>> _lt;
    unordered_map<int,list<pair<int,int>>::iterator> _up;
};
void test(){
    LRU l(3);
    l.put(1,2);
    l.put(2,3);
    l.put(3,4);
    l.put(4,5);
    l.display();
}
int main(int argc, char * argv[]){
    test();    
    return 0;
}

